#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode()
      : val(0), left(nullptr), right(nullptr){} * TreeNode(int x)
      : val(x),
        left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right)
      : val(x), left(left), right(right) {}
};
TreeNode *buildNode(const vector<int> &preorder, int preorder_start,
                    int preorder_end, const vector<int> &inorder,
                    int inorder_start, int inorder_end) {
  /*
  preorder_start:先序序列开始位置
  preorder_end:先序序列结束位置
  inorder_start:中序序列开始位置
  inorder_end:中序序列结束位置
  */
  if ((preorder_start > preorder_end) || (inorder_start > inorder_end)) {
    return nullptr;
  }
  // 构建节点
  TreeNode *root = new TreeNode(preorder[preorder_start]);
  // 在中序遍历序列中通过根节点 分割左子树和右子树的中序遍历序列
  int left_inorder_end = -1;
  for (int i = inorder_start; i <= inorder_end; i++) {
    if (inorder[i] == preorder[preorder_start]) {
      left_inorder_end = i;
      break;
    }
  }
  if (left_inorder_end == -1) {
    return nullptr;
  }
  // 计算左子树序列的长度
  int left_tree_len = left_inorder_end - inorder_start;
  root->left =
      buildNode(preorder, preorder_start + 1, preorder_start + left_tree_len,
                inorder, inorder_start, inorder_start + left_tree_len);
  root->right =
      buildNode(preorder, preorder_start + left_tree_len + 1, preorder_end,
                inorder, left_inorder_end + 1, inorder_end);
  return root;
}

TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
  TreeNode *root = buildNode(preorder, 0, preorder.size() - 1, inorder, 0,
                             inorder.size() - 1);
  return root;
}

// 优化时间复杂度 -> 减少查询时间

TreeNode *buildNode_(const vector<int> &preorder, int preorder_start,
                     int preorder_end, const vector<int> &inorder,
                     int inorder_start, int inorder_end,
                     const unordered_map<int, int> &_map) {
  /*
  preorder_start:先序序列开始位置
  preorder_end:先序序列结束位置
  inorder_start:中序序列开始位置
  inorder_end:中序序列结束位置
  */
  if ((preorder_start > preorder_end) || (inorder_start > inorder_end)) {
    return nullptr;
  }
  // 构建节点
  TreeNode *root = new TreeNode(preorder[preorder_start]);
  // 在中序遍历序列中通过根节点 分割左子树和右子树的中序遍历序列
  int left_inorder_end = -1;
  auto it = _map.find(preorder[preorder_start]);
  if (it != _map.end()) {
    left_inorder_end = it->second;
  }
  if (left_inorder_end == -1) {
    return nullptr;
  }
  // 计算左子树序列的长度
  int left_tree_len = left_inorder_end - inorder_start;
  root->left =
      buildNode(preorder, preorder_start + 1, preorder_start + left_tree_len,
                inorder, inorder_start, inorder_start + left_tree_len);
  root->right =
      buildNode(preorder, preorder_start + left_tree_len + 1, preorder_end,
                inorder, left_inorder_end + 1, inorder_end);
  return root;
}

TreeNode *buildTree_(vector<int> &preorder, vector<int> &inorder) {
  unordered_map<int, int> inorder_idx_map;
  for (int i = 0; i < inorder.size(); ++i) {
    inorder_idx_map[inorder[i]] = i;
  }
  TreeNode *root = buildNode_(preorder, 0, preorder.size() - 1, inorder, 0,
                              inorder.size() - 1, inorder_idx_map);
  return root;
}